package datastructure;

import java.util.ArrayList;
import java.util.List;

public class  TreeNode {

    private int val;
    private TreeNode left;
    private TreeNode right;
    public TreeNode() {};
    public TreeNode(int val) { this.val = val; }
    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public TreeNode getLeft() {
        return left;
    }

    public void setLeft(TreeNode left) {
        this.left = left;
    }

    public TreeNode getRight() {
        return right;
    }

    public void setRight(TreeNode right) {
        this.right = right;
    }

    /*
        针对783题，给出一个数组，按照层级遍历的方式变成二叉数
         */
    public static TreeNode arrayToTree(List<Integer> ints) {

        List<TreeNode> array = new ArrayList<>();
        for (Integer anInt : ints) {
            if (anInt != null) {
                TreeNode node = new TreeNode(anInt, null, null);
                array.add(node);
            } else {
                array.add(null);
            }
        }

       // 构建二叉树
        if (array.size() > 0){
            for (int i = 0; i < ints.size() / 2 - 1; i++) {    // i表示的是根节点的索引，从0开始
                if (array.get(2 * i + 1) != null) {
                    // 左结点
                    array.get(i).left = array.get(2 * i + 1);
                }
                if (array.get(2 * i + 2) != null) {
                    // 右结点
                    array.get(i).right = array.get(2 * i + 2);
                }
            }
            // 判断最后一个根结点：因为最后一个根结点可能没有右结点，所以单独拿出来处理
            int lastIndex = ints.size() / 2 - 1;
            // 左结点
            if (array.get(lastIndex * 2 + 1) != null){
                array.get(lastIndex).left = array.get(lastIndex * 2 + 1);
            }
            // 右结点，如果数组的长度为奇数才有右结点
            if (ints.size() % 2 == 1 && array.get(lastIndex * 2 + 2) != null) {
                array.get(lastIndex).right = array.get(lastIndex * 2 + 2);
            }
        }
        return array.get(0);
    }


    /*
    打印数组 使用先序
     */
    public static void print(TreeNode node) {
        if (node != null) {
            System.out.print(node.val + " ");
            print(node.left);
            print(node.right);
        }
    }
}
